//! Common logic shared by the taint analysis and the rewriting tools.

use crate::{
    analysis,
    constants::*,
    ptr_provenance::{Loc, PtrProvenanceAnalysis, POISON_SIGS_OF_FN_PTRS},
    rustc_ast::ast::LitKind,
    rustc_hir::*,
    rustc_lint::LateContext,
    types::{FnSig, Lifetime, *},
    util::{HashMap, HashSet},
};
use def_id::{DefId, LOCAL_CRATE};
use itertools::Itertools;
use std::{
    fmt::{Debug, Write},
    panic,
    sync::atomic::Ordering,
};

/// Checks if the given function is generated by the compiler or our
/// macros.
pub fn is_synthetic_fn(_fn_decl: &FnDecl<'_>, body: &Body<'_>) -> bool {
    body.value.span.from_expansion()
}

/// Returns the name of the definition at given HIR node in current crate
pub fn get_hir_qname(ctx: &LateContext<'_>, hir_id: HirId) -> FnName {
    let def_id = DefId {
        krate: LOCAL_CRATE,
        index: ctx.tcx.hir().local_def_id(hir_id).local_def_index,
    };
    ctx.get_def_path(def_id)
        .iter()
        .map(|segment| segment.to_string())
        .filter(|s| !s.is_empty())
        .join("::")
}

pub fn get_def_qname<'tcx>(ctx: &LateContext<'tcx>, def_id: DefId) -> FnName {
    ctx.get_def_path(def_id)
        .into_iter()
        .map(|segment| segment.to_string())
        .filter(|s| !s.is_empty())
        .join("::")
}

/// Check if given expression is a call to size_of, possibly nested in
/// casts
pub fn is_size_of(ctx: &LateContext, expr: &Expr) -> bool {
    if let ExprKind::Cast(e, _) = &expr.kind {
        // some programs cast the result of size_of to size_t
        is_size_of(ctx, e)
    } else if let ExprKind::Call(
        Expr {
            kind: ExprKind::Path(inner_callee_path),
            hir_id,
            ..
        },
        [],
    ) = &expr.kind
    {
        let inner_callee = qpath_to_segments(ctx, inner_callee_path, *hir_id)
            .into_iter()
            .map(|s| s.to_string())
            .join("::");
        inner_callee == "core::mem::size_of" || inner_callee == "std::mem::size_of"
    } else {
        false
    }
}

/// Check if we can potentially rewrite this call to malloc/calloc, assuming it
/// is not poisoned. Returns `false` if `call` is not a function call
/// expression. If no struct info is given then the malloc is optimistically
/// assumed to be rewritable.
///
/// Arguments:
///
///  - `call`: The call expression
///
///  - `ty`: The type the result of the call is cast to, all calls to
///  malloc/calloc are wrapped in a cast.
pub fn can_rewrite_allocation(
    struct_info: Option<&StructInfo>,
    ctx: &LateContext,
    call: &Expr,
    ty: Type,
) -> bool {
    // Check the type of the value the result is cast to. We determine
    // the type of value to allocate based on the cast result.
    let check_cast_type = || {
        if let Type::Ptr(_, type_to_allocate) = &ty {
            struct_info.map_or(true, |s| s.can_generate_default(type_to_allocate))
        } else {
            log::warn!(
                "call to malloc is cast to a non-pointer type {}, at {:?}",
                ty,
                call.span
            );
            false
        }
    };

    if let ExprKind::Call(
        Expr {
            kind: ExprKind::Path(callee_path),
            hir_id,
            ..
        },
        args,
    ) = &call.kind
    {
        let callee_segments = qpath_to_segments(ctx, callee_path, *hir_id)
            .into_iter()
            .map(|s| s.to_string())
            .collect::<Vec<String>>();
        match callee_segments[callee_segments.len() - 1].as_str() {
            "malloc" => {
                assert_eq!(args.len(), 1);
                if !is_size_of(ctx, &args[0]) {
                    log::warn!(
                        "cannot rewrite malloc, inner expression at: {:?}",
                        call.span
                    );
                    return false;
                }
                check_cast_type()
            },
            "calloc" => {
                assert_eq!(args.len(), 2);
                // some programs mix up the size and the count
                // arguments of calloc, so we need to test for
                // both permutations
                if (is_size_of(ctx, &args[0])
                    && matches!(get_constant_value(&args[1]), Some(LitKind::Int(1, _))))
                    || (is_size_of(ctx, &args[1])
                        && matches!(get_constant_value(&args[0]), Some(LitKind::Int(1, _))))
                {
                    check_cast_type()
                } else {
                    log::warn!(
                        "cannot rewrite calloc, it is not called with arguments like (size_of<T>, 1) or (1, size_of<T>), at {:?}",
                        call.span
                    );
                    false
                }
            },
            _ => false,
        }
    } else {
        false
    }
}

/// Flatten all segments in a given path
pub fn flatten_path(path: &Vec<Segment>) -> Vec<Name> {
    path.iter().map(|segment| segment.flatten()).collect()
}

/// Information about a Rust enum
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct Enum {
    pub name: Name,
    /// We represent each variant as a struct
    pub variants: Vec<Struct>,
}

/// A node in the struct containment/points-to graph
#[derive(Clone, PartialEq, Eq, Hash, Debug, PartialOrd, Ord)]
pub enum Node {
    /// A normal node representing a struct
    Struct(Name),
    /// A node representing a function pointer field with an associated location
    FnPtr(Loc<Name>, FnSig),
    /// A node representing a named function, this is used in the rewriting
    /// engine to represent functions, but not used as part of the points-to
    /// graph
    Fn(Name),
}

/// An edge in the struct points-to graph. For regular structs, it is a field
/// name. For function pointers, it denotes an argument position or return
/// value.
#[derive(Clone, PartialEq, Eq, Hash, Debug, PartialOrd, Ord)]
pub enum Link {
    Field(Name),
    Param(usize),
    RetVal,
}

/// Representation of a Rust struct
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct Struct {
    /// Qualified name of the struct. This uniquely identifies the struct.
    pub name: Name,
    /// Bound lifetimes of the struct. These are variables that occur
    /// in the fields below (there may be free variables if there are
    /// nested structure definitions but they don't appear in Rust
    /// code generated from C).
    pub lifetime_quals: Vec<Lifetime>,
    /// Lifetime bounds/constraints for struct parameters
    pub lifetime_bounds: Vec<(Lifetime, Lifetime)>,
    /// The fields and their types
    pub fields: Vec<(Name, Type)>,
}

/// Points-to graph with strongly-connected components (SCCs)
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct PointsToGraph {
    /// normal adjacency map of the points-to graph
    pub graph: HashMap<Node, HashMap<Link, Node>>,
    /// scc look-up table from struct name to SCC ID
    pub sccs: HashMap<Node, u32>,
    /// reverse scc look-up table from SCC ID to the structs it contains
    pub scc_contents: HashMap<u32, HashSet<Node>>,
    /// the points-to graph of SCCs, each edge is labeled with struct &
    /// field name (e.g. Foo::bar) to uniquely identify field names
    /// shared by multiple structs
    pub scc_graph: HashMap<u32, HashMap<(Node, Link), u32>>,
}

impl PointsToGraph {
    pub fn new() -> Self {
        PointsToGraph {
            graph: HashMap::default(),
            sccs: HashMap::default(),
            scc_contents: HashMap::default(),
            scc_graph: HashMap::default(),
        }
    }

    /// Compute an SCC that the argument belongs to using Tarjan's
    /// algorithm, this is to be called from `compute_sccs`
    fn compute_scc(
        sccs: &mut HashMap<Node, u32>,
        scc_contents: &mut HashMap<u32, HashSet<Node>>,
        graph: &HashMap<Node, HashMap<Link, Node>>,
        v: Node,
        stack: &mut Vec<Node>,
        on_stack: &mut HashSet<Node>,
        last_scc: &mut u32,
        lowlink: &mut HashMap<Node, u32>,
    ) {
        let scc = *last_scc;
        *last_scc += 1;
        sccs.insert(v.clone(), scc);
        lowlink.insert(v.clone(), scc);
        stack.push(v.clone());
        on_stack.insert(v.clone());

        // visit successors of v and compute their SCCs
        for w in graph[&v].values() {
            if !sccs.contains_key(w) {
                // recursively compute the scc for w
                Self::compute_scc(
                    sccs,
                    scc_contents,
                    graph,
                    w.clone(),
                    stack,
                    on_stack,
                    last_scc,
                    lowlink,
                );
                // update the lowlink of v, in case we ended up on a cycle through w
                *lowlink.get_mut(&v).unwrap() = lowlink[&v].min(lowlink[w]);
            } else if on_stack.contains(w) {
                // w is on the stack so it is in the current SCC (we visited it earlier!)
                *lowlink.get_mut(&v).unwrap() = lowlink[&v].min(sccs[w]);
            }
        }

        // if v is a root node (the lowlink didn't get lowered), then
        // generate an SCC
        if lowlink[&v] == scc {
            let mut nodes_in_scc = HashSet::default();
            while let Some(w) = stack.pop() {
                on_stack.remove(&w);
                *sccs.get_mut(&w).unwrap() = scc;
                if w == v {
                    break;
                }
                nodes_in_scc.insert(w);
            }
            nodes_in_scc.insert(v);
            scc_contents.insert(scc, nodes_in_scc);
        }
    }

    pub fn compute_sccs(&mut self) {
        self.sccs = HashMap::default();
        self.scc_graph = HashMap::default();

        let mut stack = Vec::new();
        let mut on_stack = HashSet::default();
        let mut last_scc = 0;
        // the lowest SCC ID that a node can point to
        let mut lowlink = HashMap::default();

        // println!("points-to graph: {:#?}", self.graph);

        // use Tarjan's algorithm on each element to compute sccs
        for v in self.graph.keys() {
            if !self.sccs.contains_key(v) {
                Self::compute_scc(
                    &mut self.sccs,
                    &mut self.scc_contents,
                    &self.graph,
                    v.clone(),
                    &mut stack,
                    &mut on_stack,
                    &mut last_scc,
                    &mut lowlink,
                );
            }
        }

        // traverse the graph to build the SCC graph
        for (source, targets) in &self.graph {
            let target_sccs = self
                .scc_graph
                .entry(self.sccs[source])
                .or_insert(HashMap::default());
            for (field, target) in targets {
                target_sccs.insert((source.clone(), field.clone()), self.sccs[target]);
            }
        }
    }

    /// Returns the points-to graph node for given type, while inserting the relevant nodes to the points-to graph
    fn get_node_for(
        &mut self,
        ty: &Type,
        loc: Loc<Name>,
        ptr_provenance: &PtrProvenanceAnalysis,
    ) -> Option<Node> {
        match ty {
            Type::Ptr(_, box Type::Struct(target)) => Some(Node::Struct(target.clone())),
            Type::OptionT(box Type::Fn(sig)) => {
                Some(self.insert_fn_ptr_to_points_to_graph(loc, sig, ptr_provenance))
            },
            _ => None,
        }
    }

    fn insert_fn_ptr_to_points_to_graph(
        &mut self,
        loc: Loc<Name>,
        sig: &FnSig,
        ptr_provenance: &PtrProvenanceAnalysis,
    ) -> Node {
        let fn_node = Node::FnPtr(loc.clone(), sig.clone());
        self.graph
            .entry(fn_node.clone())
            .or_insert(HashMap::default());

        let (param_locs, ret_locs) = ptr_provenance.project_lambdas(&loc, sig.known_arity());
        // Create the edges from the function pointer field as well
        for (i, t) in sig.param_types.iter().enumerate() {
            if let Some(target) = param_locs
                .get(i)
                .map(|l| l.iter().next().unwrap().clone())
                .and_then(|param_loc| self.get_node_for(t, param_loc, ptr_provenance))
            {
                self.graph
                    .get_mut(&fn_node)
                    .unwrap()
                    .insert(Link::Param(i), target);
            } else if !(t.is_primitive() || matches!(t, Type::Ptr(_, t1) if t1.is_primitive())) {
                log::warn!(
                    "Failed to get a node for {:?}#{} : {:?} [{}]",
                    loc,
                    i,
                    t,
                    t.get_pointee().map_or(t.ctor_string(), |s| s.ctor_string())
                );
            }
        }
        if let Some(ret_loc) = ret_locs.iter().next().cloned() {
            if let Some(target) = self.get_node_for(sig.ret_type.as_ref(), ret_loc, ptr_provenance)
            {
                self.graph
                    .get_mut(&fn_node)
                    .unwrap()
                    .insert(Link::RetVal, target);
            }
        }
        fn_node
    }

    /// Inserts given struct (and its fn pointer fields) to the points-to graph
    pub fn process_struct_def(
        &mut self,
        name: &Name,
        strukt: &Struct,
        ptr_provenance: &PtrProvenanceAnalysis,
    ) {
        let source_node = Node::Struct(name.clone());
        // Insert an entry for this struct, in case it has no fields
        self.graph
            .entry(source_node.clone())
            .or_insert(HashMap::default());

        for (field, ty) in &strukt.fields {
            // TODO(maemre): also handle options, boxes, references and other references here
            let target =
                self.get_node_for(ty, Loc::Access(name.clone(), field.clone()), ptr_provenance);
            let targets = self.graph.get_mut(&source_node).unwrap();
            if let Some(target) = target {
                targets.insert(Link::Field(field.clone()), target);
            }
        }
    }
}

#[derive(Copy, Clone, PartialEq, Eq, Debug)]
// 函数的分类
pub enum FnFlavor {
    Normal,
    UsedAsFnPtr,
    Extern,
}

/// Result of struct info pass
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct StructInfo {
    /// A graph of which struct (or function signature) contains or points to
    /// which structs, and over which fields. For example, if we have a program
    /// fragment like,
    ///
    /// ```
    /// struct Foo {
    ///     bar: i32,
    ///     f: fn(Widget) -> i8,
    /// }
    /// struct Baz {
    ///     quux: Foo,
    ///     jazz: * const Baz,
    /// }
    /// struct Widget {
    /// }
    /// ```
    ///
    /// Then the contains graph will contain `[Foo -> [Widget], Baz -> [Foo,
    /// Baz, Widget], Widget -> []]`.
    pub contains_graph: HashMap<Node, HashSet<Node>>,
    /// A graph of which struct (or function signature) physically contains
    /// which other structs, and over which fields. Note that this ignores
    /// pointers and functions. For example, if we have a program fragment like,
    ///
    /// ```
    /// struct Foo {
    ///     bar: i32,
    ///     f: fn(Widget) -> i8,
    ///     y: Gadget,
    ///     r: [Obj; 32],
    /// }
    /// struct Baz {
    ///     quux: Foo,
    ///     jazz: * const Baz,
    /// }
    /// struct Widget {}
    /// struct Gadget {}
    /// struct Obj {}
    /// ```
    ///
    /// Then the contains graph will contain `[Foo -> [Gadget, Obj], Baz -> [Foo,
    /// Gadget, Obj], Gadget -> [], Widget -> []]`.
    ///
    /// Note that this graph is always acyclic.
    pub structs_inside: HashMap<Node, HashSet<Node>>,
    /// The structs and function pointers inside structs that occur in
    /// external API signatures
    pub occurs_in_external_apis: HashSet<Node>,

    /// A graph that tracks pointer fields, and records which field
    /// point to which other struct. The SCCs derived from this graph
    /// are used for generating lifetimes for reference fields
    pub points_to_graph: PointsToGraph,

    pub struct_defs: HashMap<Name, Struct>,
    pub enum_defs: HashMap<Name, Enum>,
    /// Represent unions also as structs
    pub union_defs: HashMap<Name, Struct>,
    pub type_defs: HashMap<Name, Type>,
    /// Function signatures, used for tainting structs based on
    /// whether they are involved in external APIs. The Boolean part
    /// denotes whether the function belongs to an external API or
    /// used as a function pointer.
    pub fn_sigs: HashMap<Name, (FnSig, FnFlavor)>,

    /// Internally-used mapping of named types to the types they represent to resolve syntactic types.
    type_mapping: HashMap<Name, Type>,

    /// Whether a struct has any owned pointers (thus rendering it non-copyable)
    pub has_boxes: HashSet<Node>,
}

impl StructInfo {
    pub fn new() -> Self {
        StructInfo {
            contains_graph: HashMap::default(),
            occurs_in_external_apis: HashSet::default(),
            points_to_graph: PointsToGraph::new(),
            structs_inside: HashMap::default(),
            struct_defs: HashMap::default(),
            enum_defs: HashMap::default(),
            union_defs: HashMap::default(),
            type_defs: HashMap::default(),
            fn_sigs: HashMap::default(),
            type_mapping: HashMap::default(),
            has_boxes: HashSet::default(),
        }
    }

    /// Looks up the type with given name in all the definitions. This
    /// function clones the types defined in typedefs. Avoiding that
    /// cloning (or having a shallow clone) requires [`Type`] using an
    /// arena and references, but we are deliberately avoiding it for
    /// the sake of simplicity.
    pub fn find_type(&self, name: &Name) -> Option<Type> {
        if self.struct_defs.contains_key(name) {
            Some(Type::Struct(name.clone()))
        } else if self.enum_defs.contains_key(name) {
            Some(Type::Enum(name.clone()))
        } else if self.union_defs.contains_key(name) {
            Some(Type::Union(name.clone()))
        } else {
            self.type_defs.get(&name).map(|ty| ty.clone())
        }
    }

    /// Whether the given type name is or contains (not points to!) a union
    /// 能不能生成默认值(初始值)
    /// 和resolve-lifetime.rs中的fn default_value(ty: &Type) -> Option<String>有关
    pub fn can_generate_default(&self, ty: &Type) -> bool {
        use Type::*;
        match ty {
            Struct(name) => self.struct_defs[name]
                .fields
                .iter()
                .all(|(_, t)| self.can_generate_default(t)),
            Union(_) => false,
            OptionT(_) => true,
            Ptr(..) => true,
            Tuple(tys) => tys.iter().all(|ty| self.can_generate_default(ty)),
            Array(inner, Some(_)) => self.can_generate_default(&**inner),
            Array(_, _) => false, // cannot generate default values for arrays with unknown size
            App(inner, _) => self.can_generate_default(&**inner),
            Unknown(path) if IMPLEMENTS_DEFAULT.contains(&flatten_path(path)) => true,
            Unknown(_) => {
                log::warn!("cannot generate default values for {}", ty);
                false
            },
            Bool | Char | Int(_) | Uint(_) | Float(_) => true,
            Never => false,
            _ => false,
        }
    }

    /// Walk the type and resolve syntactic types based on the type resolutions built so far
    pub fn resolve_type(&self, ty: &Type) -> Type {
        Self::resolve_syntactic_type(&self.type_mapping, ty)
    }

    /// Walk the type and resolve syntactic types that occur in it
    fn resolve_syntactic_type(type_mapping: &HashMap<Name, Type>, ty: &Type) -> Type {
        let f = |ty| Self::resolve_syntactic_type(type_mapping, ty);

        match ty {
            Type::OptionT(inner) => Type::OptionT(Box::new(f(inner))),
            Type::Tuple(fields) => Type::Tuple(fields.iter().map(f).collect()),
            Type::Array(inner, size) => Type::Array(Box::new(f(inner)), size.clone()),
            Type::Slice(inner) => Type::Slice(Box::new(f(inner))),
            Type::Fn(fn_sig) => Type::Fn(FnSig {
                param_types: fn_sig.param_types.iter().map(f).collect(),
                ret_type: Box::new(f(&*fn_sig.ret_type)),
                unsafety: fn_sig.unsafety,
                lifetime_quals: fn_sig.lifetime_quals.clone(),
                lifetime_bounds: fn_sig.lifetime_bounds.clone(),
                c_variadic: fn_sig.c_variadic,
            }),
            Type::Ptr(mutbl, inner) => Type::Ptr(*mutbl, Box::new(f(inner))),
            Type::Ref(mutbl, lifetime, inner) => {
                Type::Ref(*mutbl, lifetime.clone(), Box::new(f(inner)))
            },
            Type::Boxed(inner) => Type::Boxed(Box::new(f(inner))),
            Type::Syntactic(v) => {
                if v.len() == 1 && type_mapping.contains_key(&v[0].name) {
                    assert!(
                        v[0].generic_args.is_empty(),
                        "Cannot apply generic arguments in {:?}. Substitutions not implemented",
                        v.iter().format("::")
                    );
                    // TODO: apply lifetime args to create struct,
                    // enum, union with appropriate lifetime info
                    type_mapping[&v[0].name].clone()
                } else {
                    if v.iter().all(|segment| {
                        segment.generic_args.is_empty() && segment.lifetime_args.is_empty()
                    }) {
                        if let Some(ty) = type_mapping
                            .get(&Name::from(v.iter().map(|s| s.to_string()).join("::")))
                        {
                            ty.clone()
                        } else {
                            Type::Unknown(v.clone())
                        }
                    } else {
                        Type::Unknown(v.clone())
                    }
                }
            },
            _ => ty.clone(),
        }
    }

    /// Match syntactic types with type or struct defs. This assumes
    /// there are no (mutually) recursive types defined with typedef
    /// (e.g. `type Foo = Option<Foo>` is illegal). After this pass
    /// there should not be any instances of [`Type::Syntactic`] in
    /// any definition.
    pub fn resolve_syntactic_types(&mut self) {
        let mut type_mapping = HashMap::default();
        for name in self.struct_defs.keys() {
            type_mapping.insert(name.clone(), Type::Struct(name.clone()));
        }
        for name in self.union_defs.keys() {
            type_mapping.insert(name.clone(), Type::Union(name.clone()));
        }
        for name in self.enum_defs.keys() {
            type_mapping.insert(name.clone(), Type::Enum(name.clone()));
        }
        for (name, ty) in &self.type_defs {
            type_mapping.insert(name.clone(), ty.clone());
        }

        // Expand RHS of type definitions until reaching a
        // fixpoint. We traverse all type defs in each iteration
        // because we don't have a reverse mapping telling us which
        // type defs are affected.
        loop {
            let mut changed = false;
            for (name, ty) in &mut self.type_defs {
                let new_ty = Self::resolve_syntactic_type(&type_mapping, ty);
                if new_ty != *ty {
                    changed = true;
                    *ty = new_ty;
                    type_mapping.insert(name.clone(), ty.clone());
                }
            }
            if !changed {
                break;
            }
        }

        for struct_ in self.struct_defs.values_mut() {
            for (_, field_ty) in struct_.fields.iter_mut() {
                *field_ty = Self::resolve_syntactic_type(&type_mapping, field_ty);
            }
        }

        for struct_ in self
            .enum_defs
            .values_mut()
            .flat_map(|e| e.variants.iter_mut())
        {
            for (_, field_ty) in struct_.fields.iter_mut() {
                *field_ty = Self::resolve_syntactic_type(&type_mapping, field_ty);
            }
        }

        self.fn_sigs.values_mut().for_each(|(fn_sig, _)| {
            if let Type::Fn(new_sig) =
                Self::resolve_syntactic_type(&type_mapping, &Type::Fn(fn_sig.clone()))
            {
                *fn_sig = new_sig;
            } else {
                unimplemented!("resolving a function type should yield a function type");
            }
        });

        // save the type mapping
        self.type_mapping = type_mapping;
    }

    /// Build the dependency graph between structs and enums. This is
    /// used for finding recursive types for lifetime annotation.
    pub fn compute_struct_dependencies(&mut self, ptr_provenance: &PtrProvenanceAnalysis) {
        fn collect_mentioned_types(names: &mut HashSet<Node>, ty: &Type) {
            use Type::*;

            let mut f = |ty| collect_mentioned_types(names, ty);

            match ty {
                Struct(name) => {
                    names.insert(Node::Struct(name.clone()));
                },
                Enum(name) => {
                    names.insert(Node::Struct(name.clone()));
                },
                Union(name) => {
                    names.insert(Node::Struct(name.clone()));
                },
                OptionT(inner) => f(inner),
                Tuple(fields) => fields.iter().for_each(f),
                Array(inner, _) => f(inner),
                Slice(inner) => f(inner),
                Fn(FnSig {
                    param_types,
                    ret_type,
                    ..
                }) => {
                    param_types.iter().for_each(&mut f);
                    f(ret_type)
                },
                Ptr(_, inner) => f(inner),
                Ref(_, _, inner) => f(inner),
                Boxed(inner) => f(inner),
                Syntactic(_v) => panic!("There should not be any syntactic types at this stage"),
                _ => {},
            };
        }

        for (name, struct_) in &self.struct_defs {
            let mut names = HashSet::default();
            for (field, ty) in struct_.fields.iter() {
                collect_mentioned_types(&mut names, ty);
                if let Type::Fn(sig) = ty {
                    // Create pseudo nodes for function pointer fields
                    let fn_node =
                        Node::FnPtr(Loc::Access(name.clone(), field.clone()), sig.clone());
                    let mut names_in_fn_sig = HashSet::default();
                    collect_mentioned_types(&mut names_in_fn_sig, ty);
                    // insert the entry for the edges from the fn pointer
                    self.contains_graph.insert(fn_node.clone(), names_in_fn_sig);
                    // insert the entry for the edge to the fn pointer
                    names.insert(fn_node);
                }
            }
            self.contains_graph
                .insert(Node::Struct(name.clone()), names);
            self.points_to_graph
                .process_struct_def(name, struct_, ptr_provenance);
        }

        for (name, struct_) in &self.struct_defs {
            let mut names = HashSet::default();
            for (_, ty) in struct_.fields.iter() {
                match ty.peel_array() {
                    Type::Struct(name) | Type::Union(name) => {
                        names.insert(Node::Struct(name.clone()));
                    },
                    _ => {},
                }
            }
            self.structs_inside
                .insert(Node::Struct(name.clone()), names);
        }

        fn compute_transitive_closure<T: Clone + std::hash::Hash + Eq>(
            graph: &mut HashMap<T, HashSet<T>>,
        ) {
            for container in graph.keys().map(|l| l.clone()).collect::<Vec<T>>() {
                let mut worklist = graph[&container]
                    .iter()
                    .map(|l| l.clone())
                    .collect::<Vec<T>>();
                let mut visited = HashSet::default();

                while let Some(contained) = worklist.pop() {
                    if graph.contains_key(&contained) {
                        for child in &graph[&contained] {
                            if !visited.contains(child) {
                                worklist.push(child.clone());
                            }
                        }
                    }
                    visited.insert(contained);
                }
                graph.get_mut(&container).unwrap().extend(visited);
            }
        }

        compute_transitive_closure(&mut self.contains_graph);
        compute_transitive_closure(&mut self.structs_inside);

        self.points_to_graph.compute_sccs();
    }

    pub fn compute_occurs_in_external_apis(&mut self, extern_var_types: &Vec<Type>) {
        let resolved_extern_types = extern_var_types
            .iter()
            .map(|ty| self.resolve_type(ty))
            .collect::<Vec<Type>>();
        let occur_set = &mut self.occurs_in_external_apis;
        let root_set = occur_set
            .iter()
            .map(|node| match node {
                Node::Struct(name) => Type::Struct(name.clone()),
                Node::FnPtr(_, sig) => Type::Fn(sig.clone()),
                Node::Fn(..) => unreachable!(),
            })
            .collect::<Vec<Type>>();
        let contains_graph = &self.contains_graph;
        let points_to_graph = &self.points_to_graph.graph;
        let mut poison_occurring_structs = |ty: &Type| {
            let mut worklist = ty
                .collect_structs()
                .into_iter()
                .map(Node::Struct)
                .collect::<Vec<Node>>();
            let mut seen = HashSet::default();
            while let Some(struct_node) = worklist.pop() {
                if seen.contains(&struct_node) {
                    continue;
                }
                seen.insert(struct_node.clone());
                // insert structs contained in this struct
                if let Some(l) = contains_graph.get(&struct_node) {
                    l.iter().for_each(|node| {
                        occur_set.insert(node.clone());
                        if !seen.contains(node) {
                            worklist.push(node.clone());
                        }
                    });
                }
                // also insert the function pointers in the points-to set of this struct
                if let Some(l) = points_to_graph.get(&struct_node) {
                    l.iter().for_each(|(_, node)| {
                        occur_set.insert(node.clone());
                        if !seen.contains(node) {
                            worklist.push(node.clone());
                        }
                    });
                }
                // insert the struct itself
                occur_set.insert(struct_node);
            }
        };

        // traverse starting from the nodes already in the occurs set
        for ty in root_set {
            poison_occurring_structs(&ty);
        }

        let poison_fn_ptrs = POISON_SIGS_OF_FN_PTRS.load(Ordering::Relaxed);
        for (sig, flavor) in self.fn_sigs.values() {
            if *flavor != FnFlavor::Normal && (poison_fn_ptrs || *flavor != FnFlavor::UsedAsFnPtr) {
                sig.param_types
                    .iter()
                    .for_each(&mut poison_occurring_structs);
                poison_occurring_structs(&sig.ret_type);
            }
        }

        for ty in &resolved_extern_types {
            poison_occurring_structs(ty);
        }
    }

    /// Generates the code to compute a zero-initialized value for `ty`
    ///
    /// field_type_resolver is a function that rewrites field types if needed
    pub fn zero_initializer<'a, 'b, F: Fn(Type, Loc<Name>) -> Type + Copy>(
        &'a self,
        ty: &'b Type,
        field_type_resolver: F,
    ) -> String {
        use Type::*;

        let recur = |t: &Type| self.zero_initializer(t, field_type_resolver);

        let write_field_init = |s: &mut String, name: &Name, field: &Name, ty: &Type| {
            let field_loc = Loc::Access(name.clone(), field.clone());
            let resolved_type = field_type_resolver(self.resolve_type(ty), field_loc);
            write!(s, "{}: {}, ", field, (&recur)(&resolved_type)).unwrap();
        };

        match ty {
            Struct(name) => {
                let mut zero_initializer_s = format!("{} {{ ", mk_crate_independent_qname(name));
                for (field, ty) in &self.struct_defs[name].fields {
                    write_field_init(&mut zero_initializer_s, name, field, ty);
                }
                write!(zero_initializer_s, "}}").unwrap();
                zero_initializer_s
            },
            Enum(_name) => {
                panic!("Cannot generate default values for enums: {}", ty);
            },
            Union(name) => {
                let mut zero_initializer_s = format!("{} {{ ", mk_crate_independent_qname(name));

                // use of this variable is a hack to detect when this code is
                // running inside gen-extern-stubs rather than taking another
                // parameter.
                //
                // TODO(maemre): make this a parameter
                if CRATE_INDEPENDENT_EXTERN_NAMES.load(Ordering::Relaxed) {
                    // generate only the first union field
                    let (field, ty) = &self.union_defs[name].fields[0];
                    write_field_init(&mut zero_initializer_s, name, field, ty);
                } else {
                    for (field, ty) in &self.union_defs[name].fields {
                        write_field_init(&mut zero_initializer_s, name, field, ty);
                    }
                }
                write!(zero_initializer_s, "}}").unwrap();
                zero_initializer_s
            },
            RefCell(box inner) => format!("::std::cell::RefCell::new({})", recur(inner)),
            Unknown(path) if CONST_DEFAULT_VALUE_EXPRS.contains_key(&flatten_path(path)) => {
                CONST_DEFAULT_VALUE_EXPRS[&flatten_path(path)].to_string()
            },
            Unknown(path) if IMPLEMENTS_DEFAULT.contains(&flatten_path(path)) => {
                format!("{}::default()", ty)
            },
            Ptr(_, _) => format!("(0 as {})", ty),
            OptionT(_) => "None".to_string(),
            Bool => "false".to_string(),
            Array(inner, size) => {
                // repeat the default value because the `[e; N]` syntax requires
                // `inner` to implement `Copy`, and `Default::default()` doesn't
                // work if `size` is > 31.
                format!("[{}]", format!("{},", recur(inner)).repeat(size.unwrap()))
            },
            CustomSlice(slice_ty, inner) => match slice_ty {
                CustomSliceType::Ref(..) | CustomSliceType::RefMut(..) => {
                    panic!("Cannot generate default values for references")
                },
                CustomSliceType::Boxed(_) => {
                    "crate::__laertes_array::CustomSlice::new(Box::default())".into()
                },
                CustomSliceType::Array(CustomSliceCell::NoCell, l) => format!(
                    "crate::__laertes_array::CustomSlice::new([{}; {}])",
                    recur(inner),
                    l.unwrap()
                ),
                CustomSliceType::Array(CustomSliceCell::RefCell, l) => format!(
                    "crate::__laertes_array::CustomSlice::from_vec(vec![{}; {}])",
                    recur(inner),
                    l.unwrap()
                ),
            },
            App(ty, _) => {
                // strip lifetime application
                recur(ty)
            },
            Int(_) | Uint(_) => "0".to_string(),
            Float(_) => "0.0".to_string(),
            Fn(_) => panic!("cannot generate default for function type {:?}", ty),
            _ => todo!("generate default for {} {:?}", ty.ctor_string(), ty),
        }
    }
}

impl analysis::AnalysisResult for StructInfo {
    fn name() -> String {
        "StructInfo".to_owned()
    }
}
